package com.xzz.listnode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author: hhz
 * @create: 2021-12-15 16:19
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 *   1->4->5,
 *   1->3->4,
 *   2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 **/
public class MergeKLists {
    static class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public static ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < lists.length; i++) {
            ListNode list = lists[i];
            while (null != list){
                queue.offer(list.val);
                list = list.next;
            }
        }
        Integer head = queue.poll();
        if(null==head){
            return null;
        }
        ListNode res = new ListNode(head);
        ListNode node = res;
        while (null != queue.peek()){
            node.next = new ListNode(queue.poll());
            node = node.next;
        }
        return res;
    }
    public static ListNode mergeKLists2(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
        for (ListNode listNode : lists) {
            if(null!=listNode){
                queue.offer(listNode);
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!queue.isEmpty()) {
            ListNode poll = queue.poll();
            tail.next = poll;
            tail = tail.next;
            if(null != poll.next){
                queue.offer(poll.next);
            }
        }
        return head.next;
    }
    public static void main(String[] args) {
        ListNode list1 = new ListNode(1,new ListNode(4,new ListNode(5)));
        ListNode list2 = new ListNode(1,new ListNode(3,new ListNode(4)));
        ListNode list3 = new ListNode(2,new ListNode(6));
        ListNode[] lists = new ListNode[]{list1,list2,list3};
        ListNode listNode = mergeKLists2(lists);
        while (null != listNode){
            System.out.print(listNode.val);
            if(listNode.next!=null){
                System.out.print(",");
            }
            listNode = listNode.next;
        }
    }

}
